class Solution {
    public:
        int numDecodings(string s) {
            int len = s.size();
            if (len < 2) {
                if (s[0]=='0')
                    return 0;
                return 1;
            }

            int i = 0;
            for (; i<len; i++) {
                if (s[i] != '0')
                    break;
            }
            if (i!=0) {
                return 0;
            }

            int l1=0;
            int l2=0;
            int dp[len];

            dp[0] = 1;
            dp[1] = 0;
            if (s[0]=='1' || (s[0]=='2' &&s[1]<='6')) {
                dp[1]++;
            }
            if (s[1] != '0') {
                dp[1]++;
            }

            for (int i=2; i<len; i++) {
                dp[i]=0;
                if (s[i-1]=='1' || (s[i-1]=='2' &&s[i]<='6')) {
                    dp[i] += dp[i-2];
                }
                if (s[i] != '0') {
                    dp[i] += dp[i-1];
                }
            }

            return dp[len-1];
        }
};

